package com.chj.jz.dp.class05;

public class Code03_BurstBalloons {
	/**
     * @param nums a list of integer
     * @return an integer, maximum coins
     */
    public static int maxCoins(int[] AA) {
        // Write your code here
        int n = AA.length;
        if (n == 0) {
            return 0;
        }
        
        int i, j, k, len;
        int[] A = new int[n + 2];
        A[0] = A[n + 1] = 1;
        for (i = 0; i < n; ++i) {
            A[i + 1] = AA[i];
        }
        
        n += 2;
        int[][] f = new int[n][n];
        for (i = 0; i < n - 1; ++i) {
            f[i][i+1] = 0; // balloon balloon
        }
        
        for (len = 3; len <= n; ++len) {
            for (i = 0; i <= n - len; ++i) {
                j = i + len - 1;
                f[i][j] = Integer.MIN_VALUE;
                for (k = i + 1; k < j; ++k) {
                    f[i][j] = Math.max(f[i][j], f[i][k] + f[k][j] + A[i] * A[k] * A[j]);
                }
            }
        }
        
        return f[0][n - 1];
    }
    
    public static void main(String[] args) {
		{
			int[] arrK = new int[] { 4, 1, 5, 10 };
			System.out.println(maxCoins(arrK));
		}
		{
			int[] arrK = new int[] { 3, 1, 5 };
			System.out.println(maxCoins(arrK));
		}
	}
}
